from typing import List

MIN_INT = -10 ** 9


class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)

        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                dp[i][j] = max(nums1[i] * nums2[j] + (dp[i - 1][j - 1] if i > 0 and j > 0 else 0),
                               dp[i - 1][j] if i > 0 else 0,
                               dp[i][j - 1] if j > 0 else 0)

        if dp[-1][-1] > 0:
            return dp[-1][-1]
        else:
            return - abs(min(abs(num) for num in nums1)) * abs(min(abs(num) for num in nums2))


if __name__ == "__main__":
    print(Solution().maxDotProduct(nums1=[2, 1, -2, 5], nums2=[3, 0, -6]))  # 18
    print(Solution().maxDotProduct(nums1=[3, -2], nums2=[2, -6, 7]))  # 21
    print(Solution().maxDotProduct(nums1=[-1, -1], nums2=[1, 1]))  # -1

    # 测试用例54/61 : 200
    print(Solution().maxDotProduct(nums1=[-3, -8, 3, -10, 1, 3, 9], nums2=[9, 2, 3, 7, -9, 1, -8, 5, -1, -1]))
